package com.lun.swordtowardoffer2.c12;

import com.lun.util.SinglyLinkedList.ListNode;

public class SortList {

	public ListNode sortList(ListNode node) {
		
		if(node == null || node.next == null) {
			return node;
		}
		
		ListNode head1 = node;
		ListNode head2 = split(node);
		
		head1 = sortList(head1);
		head2 = sortList(head2);
		
		return merge(head1, head2);
	}
	
	private ListNode split(ListNode head) {
		ListNode slow = head, fast = head.next;
		
		while(fast != null) {
			fast = fast.next;
			if(fast != null) {
				fast = fast.next;
				slow = slow.next;//先快的走完两步，慢的才走一步
			}
		}
		
		ListNode second = slow.next;
		slow.next = null;//断链
		
		return second;
	}
	
	private ListNode merge(ListNode list1, ListNode list2) {
		ListNode dummy = new ListNode(-1);
		ListNode cur = dummy;
		while(list1 != null && list2 != null) {
			if(list1.val < list2.val) {
				cur.next = list1;
				list1 = list1.next;
			}else {
				cur.next = list2;
				list2 = list2.next;				
			}
			cur = cur.next;
		}
		
		cur.next = list1 == null ? list2 : list1;
		
		return dummy.next;
	}
	
}
